1. Field of the Invention
The present invention relates to an edge list constructor used in digital image processors, particularly in those with bit map display function for polygon drawing.
2. Description of the Prior Art
It is often required to fill an arbitrary closed area expressed on a two-dimensional X-Y plane with a certain pattern in some operations such as graphics display. The most typical application is to paint the inside of a polygon when coordinates of the polygon vertexes are given. If the polygon is under a certain limitation for its shape, it is easy to fill the inside. A certain limitation here means, for example, the one in a polygon shown in FIG. 16A. In general, a polygon refers to a single closed area as shown in FIG. 16A or 16B, but the description here also covers those with crossing edges, or those with more than one closed area. It is relatively easy to define the inside area of the polygons in FIG. 16A and 16B. However, to fill a polygon in FIG. 16C, whether a point with coordinates (X#, Y#) is located inside the polygon or not needs to be judged. Typical conditions currently used for such judgment include "Even-odd rule" and "Non-zero winding rule". These two rules are described below.
Suppose m is a natural number not less than 3 and n is another natural number not more than m. Further suppose an m-polygon defined by m segments having (Xn, Yn) and (Xn+1, Yn+1), which are two adjacent elements in a coordinate vertex sequence {Xn, Yn}, as starting point and the terminating point respectively, where Xm+1=X1, and Ym+1=Y1. If the sign component of the outer product of a standard straight line starting from a coordinate point (X#, Y#) and terminating at a coordinate point at infinity and an edge starting from said (Xn, Yn) and terminating at (Xn+1, Yn+1) is Wn, then the total sum W of Wn values relating to n (W=Wn) is the winding number relating to said coordinate point (X#, Y#). This winding number is used to judge whether the coordinate point (X#, Y#) is located inside of m-polygon.
Usually, either of two criteria is selected: "a coordinate point with odd winding number is deemed to be located inside" or "a coordinate point with a winding number other than 0 is deemed to be inside". The former is called "even odd rule" and the latter "Non-zero winding rule". Refer to FIGS. 17 and 18 for instinctive understanding of these rules. Suppose the defined area of X coordinate is Xmin&lt;X. To determine the winding number of the coordinate point (X#, Y#), assume a standard segment ending at (X#, Y#) and (Xmin, Y#). When a horizontal segment (parallel to X axis) is thus selected as the standard straight line, the sign component Wn of the outer product can be easily obtained. Specifically, if there is an edge crossing this segment from -Y area toward +Y area, Wn=+1. If any edge crosses the segment from +Y area toward -Y area, Wn=-1. Accordingly, the winding number W of the coordinate point (X#, Y#) can be obtained by totaling Wn values from (Xmin, Y#) to (X#, Y#). FIG. 17 shows such a case. FIG. 18 shows an example of a polygon which most remarkably shows the difference between the even odd rule and non-zero winding rule. In FIG. 18, when {Xn, Yn} (n=1, 2, 3, 4, 5) is given, all of the areas 1 to 6 are filled according to non-zero winding rule, but only the areas 1 to 5 are filled leaving the area 6 according to the even odd rule. The even-odd rule and the non-zero winding rule have been described.
Next, a method to determine the winding number is specifically described.
The winding number can be determined by calculating the coordinates of intersections made by edges and the standard segment one by one. However, this intersection calculation processing requires division operations, resulting in low speed operation if processed by software; an expensive hardware will be required for higher speed operation. To solve this problem, various methods have been proposed taking advantage of space coherency (which means that winding numbers of adjacent coordinate points are often identical) or scan line coherency (when the winding number of the coordinate point (X#, Y#) is W, the winding numbers of the coordinate points (X#+1, Y#) and (X#-1, Y#) are often W, too). Here, referring to FIGS. 7, 8, 9A, 9B, 10A, 10B and 11, the order edge list algorithm on which the present invention is based is described.
FIG. 10A shows a triangle defined by three vertexes (4,0), (7,3) and (5,6). The three edges of the triangle are the ideal straight line drawn on the real number coordinate plane. When this triangle is mapped to integer coordinate plane, it becomes a triangle formed by three approximate lines as in FIG. 10B. One of the reasonable systems to promptly determine the coordinate values of the points constituting these approximate lines is a digital differential analyzer (DDA). Considering that edges of a polygon (approximate segments) are a set of points (hereinafter referred to as micro-points), DDA can be used to rapidly generate integer coordinates for such points. These micro-points are intersections of a horizontal straight line and an edge. For example, micro-point coordinate (5,4) in FIG. 10B is the coordinate of the intersection where an approximate segment ending at (4,0) and (5,6) crosses a horizontal straight line where Y=4. In other words, determination of micro-point coordinates using DDA is equivalent to determination of intersection points with the horizontal straight line.
FIG. 8 shows an edge list. The list contains intersections made by three approximate segments forming edges of the triangle in FIG. 10A and the horizontal straight line where Y=K (K=0, 1, 2, 3, 4, 5, 6) (i.e. the coordinates points shown as black circles in FIG. 10B) sorted by X and Y coordinate value. In addition, attribute data to indicate "+" or "-" is given to each intersection element. The attribute is "+" when the edge crosses the horizontal straight line upward from lower point, and "-" for reverse direction. This attribute data is used for increment or decrement in winding number calculation. Usually, an edge list for one horizontal straight line consists of even number of elements. If it has odd number of elements, it is inconsistent with the fact that the winding number of the coordinate point at infinity is zero.
However, the edge list for horizontal straight line where Y=6 which the vertex (5,6) as the maximum Y coordinate value belongs to consists of odd number of elements. Similarly, the edge list for the horizontal straight line where Y=4 which the minimum vertex (4,0) belongs to consists of odd number of elements. Accordingly, it is necessary to arrange the processing to allow two edge elements for a maximum or minimum point. FIG. 9A shows an edge list with such maximum and minimum value processing. This list has been modified so that it can have two equivalent values for the maximum and the minimum points. Alternatively, the list may have two edge elements for one maximum point and no edge element for one minimum point, for example. FIG. 9B shows an edge list subjected to such maximum/minimum processing.
The maximum/minimum processing can be solved in the process where approximate segments are generated by DDA. Edge list generation in FIG. 9A is described below. Generally, approximate straight lines are generated as if they trace the polygon edges in one direction along the edges. Taking the triangle in FIG. 10B as an example, an approximate straight line from (5,6) to (7,3) and that from (7,3) to (4,0) and that from (4,0) to (5,6) are generated in this order. Thus, if the terminating end of the approximate segment currently generated by DDA is the maximum or minimum point, the segment is generated up to the terminating point. If the terminating end of the approximate segment currently generated by DDA is not a maximum or minimum point, the segment is generated up to the point immediately before the terminating point. Thus, an edge list as in FIG. 9A can be constructed.
Finally, edge list in FIG. 9A or 9B is used for judgment whether a point is located inside of the polygon. When a horizontal straight line where Y=2 is taken for example, it has two elements: (4,2,+) and (6,2,-). This means that the winding number increases by 1 at the coordinate point where X=4 and decreases by 1 at a coordinate point (6,2). For the winding number at the intersection (4,2) and (6,2), certain rules can be introduced as boundary judgment conditions. The boundary judgment condition used here is: "if an intersection (X#, Y#) exists, the winding number changes at a position where (X#-0.5, Y#)". Accordingly, the winding number is 1 for the area 4&lt;X&lt;6, and 0 for the area where X&lt;4 or 6&lt;X.
When the winding numbers are determined based on FIG. 9A and the points inside of the triangle are filled, then the result is as shown in FIG. 11. The coordinate points with the winding number of 1 are filled.
In conventional ordered edge list algorithm as described above, if a polygon has some hundreds of vertexes, it takes a long time to sort the elements by X and Y coordinate values. The memory space is originally in one-dimensional disposition arranged by the address, which is only one parameter. On the other hand, an edge list is in two-dimensional array according to X and Y coordinates. There are two methods for rapid sorting when two-dimensionally arranged data are stored in one-dimensional space.
The first one is rearrangement of the memory space into a two-dimensional space. To minimize the number of coordinate points subjected to winding number judgment, the minimum circumscribing rectangle entirely enclosing the polygon (circumscribing rectangle hereinafter) is extracted so as to determine the winding number of coordinate points belonging to the internal area of the circumscribing rectangle only. FIGS. 15A and 15B show an example of such circumscribing rectangle. Circumscribing rectangle extraction is an effective means to decrease the data subjected to processing. To one coordinate point belonging to the inside of a circumscribing rectangle, an area to store the winding number of the coordinate point is assigned to the memory. In other words, the memory capacity assigned as the edge list storage area is determined uniformly depending on the size of the circumscribing rectangle. In a polygon as shown in FIG. 15B, memory efficiency is relatively high, but in a polygon as shown in FIG. 15A, efficiency is extremely low. Only 1% of the memory capacity actually assigned as the edge list storage area is used.
The second method is generation of coordinate values for the differential points forming the approximate segment from the side with larger Y values to lower values. Taking FIG. 10A as an example, by generating of the approximate straight line from (7,3) to (4,0) and that from (7,3) to (5,6) at a time, edge list elements are generated starting from those with larger Y values. In this method, however, the number of DDA systems required depends on the shape of the polygon. In an extreme case, DDA is required for the same number as the polygon edges. Thus, this is not a realistic method. Alternatively, one DDA can be used to generate two or more approximate straight lines. In this case, too, parameters DDA requires to generate straight lines must be pushed and popped between DDA and memory. Considering this overhead, this is not realistic, either.
Two methods have been described above. Memory capacity in former method and the number of DDA in the latter method are distinct problems. In short, conventional edge list storing systems have a drawback that they cannot rapidly construct an edge list when the polygon has increased vertexes.